1784B - Letter Exchange - CodeForces Solution

#include <cstdio>

#include <vector>

using namespace std;

const char ch[3] = {'w', 'i', 'n'};



int t, m, id[256];

char s[4];



vector<int> vec[3][3];



struct node{

    int a, b, c, d;

    node(int a, int b, int c, int d) : a(a), b(b), c(c), d(d){}

};

vector<node> ans;



void f(int i, int x, int y){

    if(vec[y][x].size()){

        ans.push_back(node(i, x, vec[y][x].back(), y));

        vec[y][x].pop_back();

    }

    else

        vec[x][y].push_back(i);

}



int main(){

    id['w'] = 0;

    id['i'] = 1;

    id['n'] = 2;

    scanf("%d", &t);

    while(t--){

        ans.clear();

        scanf("%d", &m);

        for (int i = 1; i <= m; i++){

            scanf("%s", s);

            bool have[3] = {};

            for (char *c = s; *c; c++)

                have[id[*c]] = true;

            bool havehave[3] = {};

            for (char *c = s; *c; c++){

                if(!havehave[id[*c]])

                    havehave[id[*c]] = true;

                else

                    for (int j = 0; j < 3; j++)

                        if(!have[j]){

                            f(i, id[*c], j);

                            have[j] = true;

                            break;

                        }

            }

        }

        while(vec[0][1].size()){

            ans.push_back(node(vec[0][1].back(), 0, vec[1][2].back(), 1));

            ans.push_back(node(vec[1][2].back(), 0, vec[2][0].back(), 2));

            vec[0][1].pop_back();

            vec[1][2].pop_back();

            vec[2][0].pop_back();

        }

        while(vec[0][2].size()){

            ans.push_back(node(vec[0][2].back(), 0, vec[2][1].back(), 2));

            ans.push_back(node(vec[2][1].back(), 0, vec[1][0].back(), 1));

            vec[0][2].pop_back();

            vec[2][1].pop_back();

            vec[1][0].pop_back();

        }

        printf("%d\n", (int)ans.size());

        for(auto nd : ans)

            printf("%d %c %d %c\n", nd.a, ch[nd.b], nd.c, ch[nd.d]);

    }

    return 0;

}